/*
https://leetcode.cn/problems/number-of-provinces/submissions/568342388/
*/
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n=isConnected.size();
        union_find uf(n);
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                if(isConnected[i][j]){
                uf.pair(j,i);
                }
            }
        }
        return uf.groupCount();
    }
    // 并查集 1
class union_find {
public:
    // 构造从 0 到 n - 1 的节点
    union_find(int n) : n(n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    // 合并两个节点
    void pair(int index1, int index2) {
        parent[find(index2)] = find(index1);
    }
    // 找到根节点
    int find(int index) {       // 递归函数，找根节点的同时进行路径压缩
        if (parent[index] != index) {
            parent[index] = find(parent[index]);
        }
        return parent[index];
    }
    // 判断连接性
    bool check(int index1, int index2) {
        return find(index1) == find(index2);
    }
    // 返回连通图的数量
    int groupCount() {      // 集合去重得到连通图的数量
        unordered_set<int> us;
        for (int i = 0; i < n; ++i) us.emplace(find(i));
        return us.size();
    } 
private:
    int *parent, n;
};
};